package ACWing.SearchAndGraphTheory.DFS;
//187. 导弹防御系统

import java.util.Scanner;

/**
 * @author :chenjie
 * @date :Created 2022/12/20 22:03
 */
public class MissileDefenseSystem {

    static int min;
    static int[]up=new int[55];
    static int[]down=new int[55];
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while (true){
            int n=sc.nextInt();
            if(n==0){
                break;
            }
            int[]arr=new int[n];
            for (int i = 0; i < n; i++) {
                arr[i]=sc.nextInt();
            }
            min=n;
            dfs(arr,0,0,0,n);
            System.out.println(min);
        }


    }
    public static void dfs(int[]arr,int su,int sd,int k,int n){
        if(su+sd>=min){
            return;
        }
        if(k==n){
            min=su+sd;
            return;
        }
        //上升序列添加找到比arr[k]小的上升序列尾部进行更新如果超过上升序列的个数便更新su
        int x=0;
        while (x<su&&up[x]>=arr[k]){x++;}
        int t=up[x];
        up[x]=arr[k];
        if(x<su){
            dfs(arr,su,sd,k+1,n);
        }else {
            dfs(arr,su+1,sd,k+1,n);
        }
        up[x]=t;
        //下降序列添加
        x=0;
        while (x<sd&&down[x]<=arr[k]){x++;}
        t=down[x];
        down[x]=arr[k];
        if(x<sd){
            dfs(arr,su,sd,k+1,n);
        }else {
            dfs(arr,su,sd+1,k+1,n);
        }
        down[x]=t;
    }
}
